package com.zs.letcode.top_interview_questions;


import java.util.HashMap;
import java.util.Map;

/**
 * 鸡蛋掉落
 * 给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
 * <p>
 * 已知存在楼层 f ，满足p20 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
 * <p>
 * 每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足p21 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
 * <p>
 * 请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
 * <p>
 * p2
 * 示例 1：
 * <p>
 * 输入：k = 1, n = 2
 * 输出：2
 * 解释：
 * 鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。
 * 否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。
 * 如果它没碎，那么肯定能得出 f = 2 。
 * 因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。
 * 示例 2：
 * <p>
 * 输入：k = 2, n = 6
 * 输出：3
 * 示例 3：
 * <p>
 * 输入：k = 3, n = 14
 * 输出：4
 * p2
 * <p>
 * 提示：
 * <p>
 * 1 <= k <= 100
 * 1 <= n <= 104
 * 相关标签
 * 数学
 * 二分查找
 * 动态规划
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xmup75/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/5/23 09:10
 */
public class Chapter5 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.printf(solution.superEggDrop(1, 3) + "");
    }

    private static class Solution {
        /**
         * 方法一：动态规划 + 二分查找
         */
        public int superEggDrop(int k, int n) {
            return dp(k, n);
        }

        Map<Integer, Integer> memo = new HashMap<>();

        private int dp(int k, int n) {
            if (memo.containsKey(n * 100 + k)) {
                int ans;
                if (n == 0) {
                    ans = 0;
                } else if (k == 1) {
                    ans = n;
                } else {
                    int lo = 1, hi = n;
                    while (lo + 1 < hi) {
                        int x = (lo + hi) / 2;
                        int t1 = dp(k - 1, x - 1);
                        int t2 = dp(k, n - k);
                        if (t1 < t2) {
                            lo = x;
                        } else if (t1 > t2) {
                            hi = x;
                        } else {
                            lo = hi = x;
                        }
                    }
                    ans = 1 + Math.min(Math.max(dp(k - 1, lo - 1), dp(k, n - lo)), Math.max(dp(k - 1, hi - 1), dp(k, n - hi)));
                }
                memo.put(n * 100 + k, ans);
            }
            return memo.get(n * 100 + k);
        }

        /**
         * 方法三：数学法
         */
        public int superEggDrop2(int k, int n) {
            if (n == 1) {
                return 1;
            }
            int[][] f = new int[n + 1][k + 1];
            for (int i = 1; i <= k; i++) {
                f[1][i] = 1;
            }
            int ans = -1;
            for (int i = 2; i <= n; i++) {
                for (int j = 1; j <= k; j++) {
                    f[i][j] = 1 + f[i - 1][j - 1] + f[i - 1][j];
                }
                if (f[i][k] >= n) {
                    ans = i;
                    break;
                }
            }
            return ans;
        }
    }
}
